//61.旋转链表
//https://leetcode.cn/problems/rotate-list/?envType=study-plan-v2&envId=top-interview-150
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return nullptr;
        ListNode* cur = head;
        int num = 0;
        while (cur)
        {
            cur = cur->next;
            ++num;
        }
        k %= num;
        if (k == 0) return head;
        cur = head;
        //找需要旋转的链表头
        for (int i = 0; i < num-k; ++i, cur = cur->next);
        //找旋转后链表的最后一个节点
        ListNode* tmp = head;
        while (tmp->next != cur) tmp = tmp->next;
        //新头节点
        ListNode* ret = cur;
        while (cur->next) cur = cur->next;
        cur->next = head;
        tmp->next = nullptr;
        return ret;
    }
};